package com.lsa.letcode.the150.evalRpn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Stack;

public class Solution {
	static Map<String, Integer> oper2Priority = new HashMap<String, Integer>();
	static Map<String, Operator> oper2Operator = new HashMap<String, Operator>();
	{
		oper2Priority.put("/", 1);
		oper2Priority.put("*", 1);
		oper2Priority.put("-", 0);
		oper2Priority.put("+", 0);
		
		oper2Operator.put("*", Operator.MULT);
		oper2Operator.put("/", Operator.DIV);
		oper2Operator.put("+", Operator.PLUS);
		oper2Operator.put("-", Operator.MINUS);
	}
	
	public int calculate(String expr) {
		String[] rpn = toRPN(expr);
		return evalRPN(rpn);
    }
	
    int evalRPN(String[] tokens) {
    	List<Object> rpn = new LinkedList<Object>();
    	for (String t : tokens) {
    		if (oper2Priority.get(t) != null) {
    			rpn.add(t);
    		}
    		else {
    			rpn.add(Long.valueOf(t));
    		}
		}
    	
    	ListIterator<Object> iter = rpn.listIterator();
    	
    	while(rpn.size() > 1) {
    		// PRE : iter is after first OP
    		while(iter.hasNext() && isNum(iter.next()));
    		
    		String op = (String)iter.previous();
    		Operator operator = oper2Operator.get(op);
    		iter.remove();
    		
    		Long operand2 = (Long)iter.previous();
    		iter.remove();
    		
    		Long operand1 = (Long)iter.previous();
    		iter.remove();
    		
    		Long result = null;
    		
    		switch (operator) {
			case PLUS:
				result = operand1 + operand2;
				break;
			case MINUS:
				result = operand1 - operand2;
				break;
			case MULT:
				result = operand1 * operand2;
				break;
			case DIV:
				result = operand1 / operand2;
				break;
			}
    		iter.add(result);
    	}
    	
        return ((Long)rpn.get(0)).intValue();
    }
    
    private boolean isNum(Object o){
    	return o instanceof Long;
    }
    
    String[] toRPN(String expr) {
    	String[] tokenz = tokenize(expr);
    	
    	List<String> tokenzRpn = new ArrayList<String>();
    	Stack<String> opers = new Stack<String>();
    	
    	for (String t : tokenz) {
    		Integer priority = oper2Priority.get(t);
    		if (priority != null){ // + OR - OR * OR /
    			while(!opers.isEmpty()) {
    				String oper = opers.peek();
    				if (!"(".equals(oper)){
    					if (compareOpers(oper, t) >= 0) {
    						tokenzRpn.add(opers.pop());
    					}
    					else {
    						break;
    					}
    				}
    				else {
    					break;
    				}
    			}
    			opers.add(t);
    		}
    		else if ("(".equals(t)) {
    			opers.add(t);
    		}
    		else if (")".equals(t)) {
    			boolean isPopped = false;
    			while(!opers.isEmpty()) {
    				String oper = opers.pop();
    				if ("(".equals(oper)) {
    					isPopped = true;
    					break;
    				}
    				else {
    					tokenzRpn.add(oper);
    				}
    			}
    			if (!isPopped) {
    				throw new RuntimeException("Syntax err");
    			}
    		}
    		else {
    			tokenzRpn.add(t);
    		}
		}
    	
    	while(!opers.isEmpty()) {
			String oper = opers.pop();
			if ("(".equals(oper) || ")".equals(oper)) {
				throw new RuntimeException("Syntax err");
			}
			tokenzRpn.add(oper);
		}
    	
    	return tokenzRpn.toArray(new String[0]);
    }
    
    int compareOpers(String o1, String o2) {
		return oper2Priority.get(o1) - oper2Priority.get(o2);
    }
    
    enum State{
		READY,
		INDIGIT
	};
	
	enum Operator{
		PLUS,
		MINUS,
		MULT,
		DIV
	}
	
    String[] tokenize(String expr) {
    	List<String> tokenz = new ArrayList<String>();
    	State state = State.READY;
    	StringBuilder current = new StringBuilder();
    	for (int i = 0; i < expr.length(); i++) {
    		char c = expr.charAt(i);
    		if (Character.isWhitespace(c)) {
    			continue;
    		}
    		if (state == State.READY) {
				if (Character.isDigit(c)){
					state = State.INDIGIT;
    				current.append(c);
    			}
				else {
					tokenz.add(String.valueOf(c));
				}
    		}
    		else { // State.INDIGIT
    			if (!Character.isDigit(c)){
					state = State.READY;
					tokenz.add(current.toString());
					current.setLength(0);
					tokenz.add(String.valueOf(c));
    			}
    			else {
    				current.append(c);
    			}
    		}
		}
    	if (state == State.INDIGIT) {
    		tokenz.add(current.toString());
    	}
    	return tokenz.toArray(new String[0]);
    }
}